package com.day01_Array;

import java.util.Arrays;

/**
 * @ClassName: Test03 数组常见算法
 * @Author: 豆豆在睡觉
 * @Create 2024/1/14-09:40
 * @Version 1.0
 */
public class Test03 {
    public static void main(String[] args) {
        // 平均值， 最大值，最小值。 总和
        // 创建一个length是10的数组， 每个值在[10, 99]之间
        int[] arr = new int[10];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 90) + 10;
            System.out.println(arr[i]);
        }

        // 最大值
        int max = arr[0];
        for(int i = 1; i < arr.length; i++) {
            if(max < arr[i]) {
                max = arr[i];
            }
        }
        System.out.println("最大值是：" + max);

        // 最小值
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(min > arr[i]) {
                min = arr[i];
            }
        }

        // 总和
        int sum = 0;
        for (int i=0; i<arr.length;i++) {
            sum += arr[i];
        }
        // 平均值
        int average = sum / arr.length;
        System.out.println("最大值："+ max + '\n' + "最小值："+ min +'\n' + "总和："+ sum +'\n' + "平均值：" + average);
        // 数据元素赋值


        // 数组的复制
        int [] array1;
        array1 = new int[]{2,3,5,7,11,13,17,19};
        for (int i = 0; i < array1.length ; i++) {
            System.out.println(array1[i]);
        }
        int[] array2 = array1;
        array2[0] = 0;
        // array1[0]  == 0 ?

        // 数组的反转
        // 方式1 首位交换就行
        int[] array3 = new int[]{1,2,3,4,5,6,7,8,9};
        System.out.println(array3);
        for (int i = 0; i < array3.length / 2; i++) {
            int tem = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 -i] = tem;

        }
        System.out.println(array3);
        // 方式二 定义2个变量去首尾交换
        for (int i = 0 , j=array3.length - 1; i < j; i++, j--) {
            int tem = arr[i];
            arr[i] = arr[j];
            arr[j] = tem;
        }

        // 方式三 不推荐 开辟一个新的数组（内存空间去反正）
        int[] newarr = new int[array3.length];
        for (int i = 0; i < newarr.length ; i++) {
            newarr[i] = array3[array3.length - 1 - i];
        }
        array3 = newarr;

        // 数组的扩容和缩容
        int [] arr2 = new int[]{1,2,3,4};
        // 将数组扩容一倍
        // 数组长度一旦确定， 长度就不能改变了； 因此必须新建数组去扩容
        int [] newarr2 = new int[arr2.length * 2];
        // 或者 int [] newarr2 = new int [arr2.length << 1];
        // 将原有数组的元素赋值到新的数组
        for (int i = 0; i < arr2.length; i++) {
            newarr2[i] = arr2[i];
        }
        arr2 = newarr2;

        // 数组缩容 int[] arr= {1,2,3,4,5,6} // 删除索引为4的元素;
        // 方式1 不新建数组
        int[] arr3 =  {1,2,3,4,5,6,7};
        int deleteIndex = 4;
        for (int i = deleteIndex; i < arr3.length - 1; i++) {
            arr3[i] = arr3[i+1];
        }
        // 最后修改最后一个元素为默认值
        arr3[arr3.length - 1] = 0;

        // 方式2: 新建数组
        int[] newarr3 = new int[arr3.length - 1];
        for (int i = deleteIndex; i < newarr3.length  ; i++) {
            newarr3[i] = arr[i+1];
        }
        // 将newarr3赋值给arr
        arr3 = newarr3;

        // 数组元素查看
        // 线性查找
        int [] arr4 = new int[]{1,33,23,45,6,774,433};
        //查找元素5是否存在在arr4中
        int target = 5;
        boolean flag = false;
        for (int i = 0; i < arr4.length; i++) {
            if(arr4[i] == target) {
                flag = true;
                break;
            }
        }
        if(flag) {
            System.out.println("找到了");
        }else {
            System.out.println("没有找到5");
        }

        int i1 = Arrays.binarySearch(arr4, 5);
        System.out.println("---binarySearch:" + i1);
        // 二分法查找，二分法查找的前提是有序的数组；且数组长度较大
        int [] arr5 = new int[] {3,6,7,11,33,76,88,99,123};
        int target5 = 33;

        int head = 0;
        int end = arr5.length - 1;

        while (head <= end) {
            int mid = (head + end) / 2;
            if(target5 == arr5[mid]) {
                System.out.println(mid);
                break;
            } else if (target5 < arr5[mid]) {
                end = mid - 1;
            }
              else  {
                head = mid + 1;
            }
        }
        if (head > end) {
            System.out.println("二分法查找未找到");
        }




        // 算法 排序
        // 冒泡排序
        // 整体思路 ： 首先相邻的两个进行比较 1跟2比较完然后2跟3比较，
        // 如果前面的数比后面的数大就进行交换‘
        // 这样第一轮比较完成后； 最后那个位置是最大的
        // 继续比较 1和2比较 2和3 比较。。。 n-2 和 n- 1比较
        //

        int[] arr6 = {43,3,56,88,3,56,77};
        // 快速排序
        // 这样第一轮是 只是找出了最大的那个，就是在最后一个位置
        for (int i = 0; i <arr6.length - 1; i++) {
            if(arr[i] > arr[i+1]) {
                int tem = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tem;
            }
        }

        // 那么这样执行多少轮呢；
        // 第一轮完成后， 最后位置最大哦
        // 第二轮开始的时候，不需要比较n个数， 完成后，
        // 最后一轮， 只需要比较 两个数；
        // 应该是n-1轮
        for(int j = 0; j<arr.length - 1; j++) {  // 总共比较几轮
            for (int i = 0; i <arr6.length - 1; i++) { // 进行比较
                if(arr[i] > arr[i+1]) {
                    int tem = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tem;
                }
            }
        }

        // 优化 第 1轮后， 第二轮只需要比较 0 - n-1位置的数
        // 第三轮开始 只需要比较 0- n-2位置的数
        for(int j = 0; j<arr.length - 1; j++) {  // 总共比较几轮
            for (int i = 0; i <arr6.length - j; i++) { // 进行比较
                if(arr[i] > arr[i+1]) {
                    int tem = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tem;
                }
            }
        }

        // 快速排序；
        // 思想：
        // 从数列中找到一个元素， 称为基准；
        // 然后把剩下的元素分成2部分 比基准小的； 比基准大的；
        // 继续将 2部分中，分开 部分1 继续找1个基准， 再进行分类
        // 部分2 中也找1个基准， 也进行分成2部分；
        // 一直到 只有1个元素位置

        // Arrays 工具类 java.utils.Arrays 包下；

    }
}
